<?php
/**
 * 快速排序
 * @param array   $seq A list of integers
 * @return array Return sorted array
 */

function quick_sort(array $seq)
{
    $len = count($seq);

    if ($len <= 1) {
        return $seq;
    }

    $left = $right = [];

    $pivot = $seq[0];
    

    while (($x = next($seq)) !== false) {
        if ($x < $pivot) {
            array_push($left, $x);
        } else {
            array_push($right, $x);
        }
    }
    return array_merge(quick_sort($left),  [$pivot], quick_sort($right));
}
